package algorithm.mycode;

import javax.sound.midi.Soundbank;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
        System.out.println(binarraySearchByRecursion(arr, 14));
    }

    public static int binarraySearchByIteration(int[] arr, int val) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int R = arr.length - 1;
        int L = 0;
        int mid = 0;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] == val) {
                return mid;
            } else if (val < arr[mid]) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return arr[L] == val ? L : -1;
    }

    public static int binarraySearchByRecursion(int[] arr, int val) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        return binarraySearchByRecursion(arr, 0, arr.length - 1, val);
    }

    public static int binarraySearchByRecursion(int[] arr, int L, int R, int val) {
        if (L < R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] == val) {
                return mid;
            } else if (arr[mid] > val) {
                return binarraySearchByRecursion(arr, L, mid - 1, val);
            } else {
                return binarraySearchByRecursion(arr, mid + 1, R, val);
            }
        }
        return arr[L] == val ? L : -1;
    }
}
